#ifndef xpack_algo_var_array
#define xpack_algo_var_array
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::algo_var_array::inc
#include"concurrency/lock/atom_swap.hpp"
#include"dumb/move.hpp"
#include"instruction/bit_test_and_reset.hpp"
#include"instruction/index_of_last_set.hpp"
#include"interface/can_alloc.hpp"
#include"interface/can_free.hpp"
#include"macro/xexport.hpp"
#include"macro/xmodify.hpp"
#include"macro/xnew.hpp"
#include"macro/xunlikely.hpp"
#include"memop/copy.hpp"
#pragma pop_macro("xuser")

namespace mixc::algo_var_array::origin {
    constexpr bool with_fixed_page_table_v = true;

    template<uxx initial_alloc_length_v, bool with_fixed_page_table_v>
    struct var_array_core {
        /* 函数：压栈
         * 参数：
         * - page_table_ptr 为指向页表数组的指针
         * - length 为数组长度指针
         * - value 为要压栈的元素
         * - alloc 为分配回调
         * - free 为回收回调
         * 注意：
         * 要求传入的 page_table_ptr 指向的是一个空指针数组（一个数组，里面的值都是 nullptr）
         */
        template<class item_t, class forward_item_t>
        static void push(
            item_t              *** page_table_ptr, 
            uxx                   * length, 
            forward_item_t       && value, 
            inc::ialloc<void>       alloc, 
            inc::ifree<void>        free){

            auto & len                  = (length[0]);
            auto & tab                  = (page_table_ptr[0]);
            auto   need_new_page        = (len & (len - 1)) == 0; // 2^n
            auto   new_tab              = (item_t **)nullptr;
            auto   ptr                  = (item_t *)nullptr;
            auto   i_page               = (uxx)0;
            auto   i                    = (uxx)0;
            auto   mask                 = (uxx)initial_alloc_length_v - 1;

            // index_of_last_set(0) -> uxx(-1)
            auto   base                 = (inc::index_of_last_set(initial_alloc_length_v - 1));

            if (len == 0) {
                if constexpr (not with_fixed_page_table_v){
                    tab                 = (item_t **)alloc(sizeof(voidp) * 2);

                    xunlikely(tab == nullptr){
                        return;
                    }
                }
                tab[0]                  = (item_t *)alloc(sizeof(item_t) * initial_alloc_length_v);
                tab[1]                  = (nullptr);

                xunlikely(tab[0] == nullptr){
                    return;
                }

                ptr                     = (tab[0]);
                len                     = (1);
                xnew (ptr) item_t(xforward(value));
                return;
            }

            // index_of_last_set(0) -> uxx(-1)
            // 当只有 0 个元素时 i = uxx(-1)，base = uxx(-1)
            // i_page = i - base = 0，依旧是我们期望的页表索引
            i                           = (inc::index_of_last_set(len | (initial_alloc_length_v - 1)));
            i_page                      = (i - base);

            // i = uxx(-1) = 0xff..ff
            // i << i = i << (i % bits(uxx))
            // 此时 mask = uxx(-1) = 0xff..ff
            mask                       |= (uxx(1) << i) - 1;

            if (need_new_page and len >= initial_alloc_length_v) {
                if (i_page % 2 == 0) { // i_page 是偶数页就需要分配新页表
                    if constexpr (not with_fixed_page_table_v){
                        new_tab         = (item_t **)alloc(sizeof(voidp) * (i_page + 2));

                        xunlikely(new_tab == nullptr){
                            return;
                        }

                        inc::copy(new_tab, tab, i_page);
                        free(tab, sizeof(voidp) * i_page);
                        tab             = (new_tab);
                    }

                    tab[i_page]         = (nullptr);
                    tab[i_page + 1]     = (nullptr);
                }

                if (tab[i_page] == nullptr){
                    tab[i_page]         = (item_t *)alloc(sizeof(item_t) * len);
                    ptr                 = (tab[i_page]);

                    xunlikely(ptr == nullptr){
                        return;
                    }
                }

                len                    += (1);
                xnew (ptr) item_t(xforward(value));
                return;
            }
            else{
                xnew (xmodify(tab[i_page][len & mask])) item_t(xforward(value));
                len                    += (1);
            }
        }

        /* 函数：退栈
         * 参数：
         * - page_table_ptr 为指向页表数组的指针
         * - length 为数组长度指针
         * - value 为要获取退栈元素的指针
         * - alloc 为分配回调
         * - free 为回收回调
         */
        template<class item_t, bool value_is_mirror_v>
        static void pop(
            item_t ***                  page_table_ptr, 
            uxx    *                    length, 
            item_t *                    value, 
            inc::ialloc<void>           alloc, 
            inc::ifree<void>            free){

            auto & len                  = (length[0]);
            auto & tab                  = (page_table_ptr[0]);
            auto & val                  = (value[0]);
            auto   new_tab              = (item_t **)nullptr;
            auto   i_page               = (uxx)0;
            auto   i                    = (uxx)0;
            auto   mask                 = (uxx)initial_alloc_length_v - 1;
            auto   base                 = (inc::index_of_last_set(initial_alloc_length_v - 1));
            auto   need_free_page       = (false);

            len                        -= (1);
            need_free_page              = (len & (len - 1)) == 0;
            i                           = (inc::index_of_last_set(len | (initial_alloc_length_v - 1)));
            i_page                      = (i - base);
            mask                       |= (uxx(1) << i) - 1;

            auto & last_value           = tab[i_page][len & mask];

            if constexpr (value_is_mirror_v){
                xnew(value) item_t(inc::move(last_value));
            }
            else{
                val                     = inc::move(last_value);
            }

            if (last_value.~item_t(); not need_free_page) {
                return;
            }
            if (len >= initial_alloc_length_v * 2 and i_page % 2 == 0){
                if (tab[i_page + 1]){
                    free(tab[i_page + 1], sizeof(item_t) * len * 2);
                }

                free(tab[i_page], sizeof(item_t) * len);

                if constexpr (not with_fixed_page_table_v){
                    new_tab             = (item_t **)alloc(sizeof(voidp) * i_page);

                    xunlikely(new_tab == nullptr){
                        return;
                    }

                    inc::copy(new_tab, tab, i_page);
                    free(tab, sizeof(voidp) * (i_page + 2));
                    tab                 = new_tab;
                }
                return;
            }
            if (len == 0){
                free(tab[0], sizeof(item_t) * initial_alloc_length_v);
                free(tab[1], sizeof(item_t) * initial_alloc_length_v);

                if constexpr (not with_fixed_page_table_v){
                    free(tab, sizeof(voidp)  * 2);
                    tab                 = nullptr;
                }
            }
        }
    };
}

namespace mixc::algo_var_array::origin {
    constexpr bool with_fixed_page_table = true;

    /* 结构：可变长度数组模板
     * 参数：
     * - initial_alloc_length_v 为数组的起始分配长度，需要二进制对齐且大于 0
     *   只有第一次和第二次分配时，分配长度为 initial_alloc_length_v，此后每次变为之前的两倍
     * - with_fixed_page_table_v 指示是否使用固定大小的页表
     * 注意：
     * - 创建数组只有在添加元素后才会分配内存
     * - 使用 with_fixed_page_table_v 选项后，将不再单独为 page_table_ptr 分配和释放内存
     *   内部假定 page_table_ptr 指向可用的内存
     */
    template<uxx initial_alloc_length_v = 1, bool with_fixed_page_table_v = not with_fixed_page_table>
    requires(
        (initial_alloc_length_v & (initial_alloc_length_v - 1)) == 0 and initial_alloc_length_v > 0
    )
    struct var_array {
        /* 函数：压栈
         * 参数：
         * - page_table_ptr 为指向页表数组的指针
         * - length 为数组长度指针
         * - value 为要压栈的元素
         * - alloc 为分配回调
         * - free 为回收回调
         * 注意：
         * 要求传入的 page_table_ptr 指向的是一个空指针数组（一个数组，里面的值都是 nullptr）
         */
        template<class item_t, class forward_item_t>
        static void push(
            item_t                  *** page_table_ptr, 
            uxx                       * length, 
            forward_item_t           && value, 
            inc::ialloc<void>   const & alloc, 
            inc::ifree<void>    const & free
        ){
            var_array_core<initial_alloc_length_v, with_fixed_page_table_v>::push(page_table_ptr, length, xforward(value), alloc, free);
        }

        template<class item_t>
        static void pop_to_mirror(
            item_t ***              page_table_ptr, 
            uxx    *                length, 
            item_t *                value, 
            inc::ialloc<void>       alloc, 
            inc::ifree<void>        free
        ){
            var_array_core<initial_alloc_length_v, with_fixed_page_table_v>::template pop<item_t, true/*假定 value 是未初始化的内存，内部调用构造函数*/>(page_table_ptr, length, value, alloc, free);
        }

        template<class item_t>
        static void pop(
            item_t ***              page_table_ptr, 
            uxx    *                length, 
            item_t *                value, 
            inc::ialloc<void>       alloc, 
            inc::ifree<void>        free
        ){
            var_array_core<initial_alloc_length_v, with_fixed_page_table_v>::template pop<item_t, false/*假定 value 是已经初始化的对象，内部进行赋值逻辑*/>(page_table_ptr, length, value, alloc, free);
        }

        /* 函数：访问
         * 参数：
         * - page_table 为页表数组
         * - index 为要访问元素的索引
         */
        template<class item_t>
        static item_t & access(item_t ** page_table, uxx index){
            auto   i_page               = (uxx)0;
            auto   i                    = (uxx)0;
            auto   mask                 = (uxx)initial_alloc_length_v - 1;
            auto   base                 = (inc::index_of_last_set(initial_alloc_length_v - 1));

            i                           = (inc::index_of_last_set(index | (initial_alloc_length_v - 1)));
            i_page                      = (i - base);
            mask                       |= (uxx(1) << i) - 1;
            auto & val                  = (page_table[i_page][index & mask]);
            return val;
        }

        /* 函数：清空
         * 参数：
         * - page_table_ptr 为指向页表数组的指针
         * - length 为数组长度指针
         * - free 为回收回调
         */
        template<class item_t>
        static void clear(item_t *** page_table_ptr, uxx * length, inc::ifree<void> free){
            auto   len                  = inc::atom_swap<uxx>(xmodify(length[0]), 0);
            auto & tab                  = (page_table_ptr[0]);

            if (len == 0){
                return;
            }

            auto   i_page               = (uxx)0;
            auto   i                    = (uxx)0;
            auto   mask                 = (uxx)initial_alloc_length_v - 1;
            auto   current_length       = (uxx)initial_alloc_length_v;
            auto   multi                = (uxx)1;
            auto   base                 = (inc::index_of_last_set(initial_alloc_length_v - 1));

            len                        -= (1);
            i                           = (inc::index_of_last_set(len | (initial_alloc_length_v - 1)));
            mask                       |= (uxx(1) << i) - 1;
            i_page                      = (i - base);

            for(uxx i = 0; i < i_page; i++){
                for(uxx j = 0; j < current_length; j++){
                    tab[i][j].~item_t();
                }

                free(tab[i], sizeof(item_t) * current_length);
                tab[i]                  = nullptr;
                current_length          = initial_alloc_length_v * multi;
                multi                  *= 2;
            }

            for(uxx i = 0; i <= (len & mask); i++){
                tab[i_page][i].~item_t();
            }

            free(tab[i_page], sizeof(item_t) * current_length);
            tab[i_page]                 = nullptr;

            if (i_page % 2 == 0 and tab[i_page += 1] != nullptr){
                if (i_page > 1){
                    current_length     *= 2;
                }
                free(tab[i_page], sizeof(item_t) * current_length);
                tab[i_page]             = nullptr;
            }

            if constexpr (not with_fixed_page_table_v){
                free(tab, sizeof(voidp) * (i_page + 1));
                tab                     = nullptr;
            }
        }
    };
}

#endif

xexport_space(mixc::algo_var_array::origin)
